1302. Almost Prime Numbers

 

Almost prime numbers are the non-prime numbers which are divisible by only a single prime number. In this problem your job is to write a program which finds out the number of almost prime numbers within a certain range.

 

Input. First line of the input file contains an integer n (n ≤ 600) which indicates how many sets of inputs are there. Each of the next n lines make a single set of input. Each set contains two integer numbers low and high (0 < low £ high < 1012).

 

Output. For each line of input except the first line you should produce one line of output. This output line contains a single integer, which indicates how many almost prime numbers are within the given range (inclusive) [low.. high].

 

Sample input

Sample output

 
3
1 10
1 20

1 5

3

4

1

 

 

SOLUTION

sieve of Eratosthenes – binary search

 

Algorithm analysis

Almost prime numbers have the form pk,  where p is a prime number, k ³ 2. For example, the almost prime numbers are 4, 8, 16, 32, 9, 81, … . As high < 1012, then from the definition of almost prime number p < 106. Generate the array primes if length 1000000 = 106, where primes[i] = 1 if i is prime and primes[i] = 0 otherwise. Then generate and sort in array m all the almost primes (their amount equals to 80070).

Let f(a, b) be the number of almost primes in the range [a..b]. Then

f(low, high) = f(1, high) – f(1, low – 1)

The number of almost primes in the range [1 .. n] equals to the position (index), where it is possible to insert n into the sorted array m by upper bound preserving the sorted order. The index number can be found using binary search on array m by means of function upper_bound.

 

Example

Let’s generate all the almost prime numbers in the range from 1 to 100. First write the powers of 2 not greater than 100. Then the powers of 3, 5 and 7. The square of 11 is greater than 100, so there are no powers of 11 among the almost primes in the range [1..100].

Sort the array:

Consider the second test case. In the range from 1 to 20 there are 4 almost prime numbers: 4, 8, 9, 16.

 

Algorithm realization

Function gen_primes fills the array primes for primality testing.

 

void gen_primes(void)

{

  int i, j;

  for(i = 0;i < MAX; i++) primes[i] = 1;

  for(i = 2; i < sqrt(MAX); i++)

    if (primes[i])

      for(j = i * i; j < MAX; j += i) primes[j] = 0;

}

 

For each prime i put into array m the numbers i2, i3, i4, … until the current power is not greater than 1012. The variable ptr contains the index of the last almost prime number that is put into array m. As the almost primes are limited by the value 1012, we need to process 64 bit integers (long long type). Place at the end of array m any number greater 1012. Let it be 1012 + 1. This should be done for binary search function to work correctly.

 

ptr = -1;

for (i = 2; i < MAX; i++)

  if (primes[i])

  {

    temp = i;

    while ((temp *= i) < 1e12)

      m[++ptr] = temp;

  }

m[++ptr] = 1e12 + 1;

 

Sort the array m using STL:

 

sort(m,m+ptr);

 

Read the number of input test cases n and for each interval [a, b] find and print the value f(a, b) = f(1, b) – f(1, a – 1) in constant time.

 

scanf("%d",&n);

for(test = 1; test <= n; test++)

{

  scanf("%lld %lld",&a,&b);

  printf("%d\n",upper_bound(m,m+ptr,b) - upper_bound(m,m+ptr,a-1));

}

 

Java realization

 

import java.util.*;

 

public class ex

{

  public static ArrayList<Long> primes = new ArrayList<Long>();

 

  public static void GenPrimes()

  {

    final int MAX_SIZE = 1000001;  

    BitSet bits = new BitSet(MAX_SIZE);

 

    bits.set(2, MAX_SIZE, true);

    for (int i = 2; i < Math.sqrt(MAX_SIZE); i++)

    {

      if (bits.get(i))

        for (int j = i * i; j < MAX_SIZE; j += i)

          bits.set(j, false);

    }

   

    for (int i = 2; i < MAX_SIZE; i++)

      if (bits.get(i))

      {

        long temp = i;

        while ((temp *= i) < 1000000000000L)

          primes.add(temp);

      }

    primes.add(1000000000001L);

    Collections.sort(primes);

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int tests = con.nextInt();

    GenPrimes();

   

    for(int i = 0; i < tests; i++)

    {

      Long low = con.nextLong();

      Long high = con.nextLong();

      int lIndex = Collections.binarySearch(primes, low);

      if (lIndex < 0) lIndex = -(lIndex + 1);

      int hIndex = Collections.binarySearch(primes, high);

      if (hIndex < 0) hIndex = -(hIndex + 1); else hIndex++;

 

      System.out.println(hIndex - lIndex);

    }

  }

}